package leetcode_周赛._2021._202104._20210411;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/4/11 10:36
 * 找出游戏的获胜者
 * 约瑟夫环问题
 * 定义一个数组，从 0 ~ n - 1，如果有人退出，则元素置为 -1
 * 找到每次报数后要删掉的数字
 */
public class _5727 {
    public static void main(String[] args) {
//        List<Integer> ans = new ArrayList<>();
//        ans.add(1);
//        ans.add(2);
//        ans.add(3);
//        System.out.println(ans);
//        System.out.println(ans.get(1));
//        ans.remove(1);
//        System.out.println(ans);
//        System.out.println(ans.get(1));
        System.out.println(new _5727().findTheWinner(5, 2));
    }

    public int findTheWinner(int n, int k) {
        List<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            nums.add(i);
        }
        int flag = 0, del = 0;
        while (del != n - 1) {
            flag = (flag + k - 1) % nums.size();
            nums.remove(flag);
            ++del;
        }
        return nums.get(nums.size() - 1);
    }
}
